package org.labuladong.动态规划算法.一维DP;

import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-17:24
 * @Description:
 *
 * 标签：动态规划，⼀维动态规划，⼆分搜索
 * 给你⼀个⼆维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和⾼度。
 * 当另⼀个信封的宽度和⾼度都⽐这个信封⼤的时候，这个信封就可以放进另⼀个信封⾥，如同俄罗斯套娃⼀样。
 * 请计算 最多能有多少个信封能组成⼀组“俄罗斯套娃”信封（即可以把⼀个信封放到另⼀个信封⾥⾯）。
 * 注意：不允许旋转信封。
 * 示例 1：
 * 输⼊：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为：[2,3] => [5,4] => [6,7]。
 *
 * 本题相当于在⼆维平⾯⾥⾯求最⻓递增⼦序列
 *
 *
 * 步骤：
 * 排序：首先，根据信封的宽度和高度对信封进行排序。
 * 我们可以首先按照宽度进行升序排序，如果宽度相同，则按照高度进行升序排序。
 * 这样，我们可以确保较小的信封出现在较大的信封之前。
 *
 * 动态规划：定义一个数组 dp，其中 dp[i] 表示以第 i 个信封结尾的最长嵌套信封序列的长度。
 * 我们的目标是找到 dp 数组中的最大值。
 *
 * 状态转移：对于每个信封 envelopes[i]，我们检查它是否可以嵌套在之前的每个信封中。
 * 如果可以，我们更新 dp[i] 为 dp[j] + 1，其中 j 是之前可以嵌套 envelopes[i] 的信封的索引。
 *
 * 更新最大长度：在每一步中，我们更新一个变量 maxLength 来记录找到的最长嵌套信封序列的长度。
 *
 *
 * @version: 1.0
 */
public class LC_354_俄罗斯套娃信封问题_binary {

	public static class Solution {
		public int maxEnvelopes(int[][] envelopes) {
			if (envelopes.length == 0)
				return 0;

			// 根据宽度和高度对信封进行排序,升序排列
			Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

			// 初始化动态规划数组
			int[] dp = new int[envelopes.length];
			int maxLength = 0;

			for (int i = 0; i < envelopes.length; i++) {
				int width = envelopes[i][0], height = envelopes[i][1];
				// 二分查找找到当前信封可以嵌套的最大信封
				int j = binarySearch(dp, 0, maxLength, height);
				// 如果没有找到可以嵌套的信封，当前信封可以作为一个新的起点
				if (j == maxLength) {
					maxLength++;
				}
				// 更新动态规划数组
				dp[j] = width;
			}

			return maxLength;
		}

		// 二分查找
//		private int binarySearch(int[] dp, int start, int end, int target) {
//			while (start < end) {
//				int mid = start + (end - start) / 2;
//				if (dp[mid] < target) {
//					start = mid + 1;
//				} else {
//					end = mid;
//				}
//			}
//			return start;
//		}

		/**
		 * 使用二分查找在动态规划数组dp中找到第一个大于或等于目标高度target的位置。
		 * 这个位置将用于确定当前信封能否替换掉最长递增子序列中的某个信封，
		 * 从而形成一个新的更长的递增子序列。
		 *
		 * @param dp 动态规划数组，存储每个信封结尾时的最长递增子序列的长度。
		 * @param start 二分查找的起始索引。
		 * @param end 二分查找的结束索引。
		 * @param target 当前信封的高度，我们希望找到一个位置，使得该位置之前的所有信封的高度都小于或等于target。
		 * @return 返回在dp数组中第一个大于或等于target的位置的索引。
		 */
		private int binarySearch(int[] dp, int start, int end, int target) {
			// 当start和end指针没有相遇时，继续进行二分查找
			while (start < end) {
				// 计算中间位置的索引
				int mid = start + (end - start) / 2;

				// 如果中间位置的信封高度小于目标高度，说明我们要找的位置在右半边
				if (dp[mid] < target) {
					start = mid + 1;
				}
				// 如果中间位置的信封高度大于或等于目标高度，说明我们要找的位置在左半边或就是中间位置
				else {
					end = mid;
				}
			}
			// 返回在dp数组中第一个大于或等于target的位置的索引
			// 如果整个数组中的所有信封高度都小于target，则start将等于end，返回start即可
			return start;
		}

		public static void main(String[] args) {
			Solution solution = new Solution();
			int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
			System.out.println(solution.maxEnvelopes(envelopes)); // 输出应该是 3
		}
	}
}
